package leetcode.matrix;

/**
 * 3 x 3 的幻方是一个填充有从 1 到 9 的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。
 *
 * 给定一个由整数组成的 grid，其中有多少个 3 × 3 的 “幻方” 子矩阵？（每个子矩阵都是连续的）。
 *
 *  
 *
 * 示例：
 *
 * 输入: [[4,3,8,4],
 *       [9,5,1,9],
 *       [2,7,6,2]]
 * 输出: 1
 * 解释:
 * 下面的子矩阵是一个 3 x 3 的幻方：
 * 438
 * 951
 * 276
 *
 * 而这一个不是：
 * 384
 * 519
 * 762
 *
 * 总的来说，在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。
 * 提示:
 *
 * 1 <= grid.length <= 10
 * 1 <= grid[0].length <= 10
 * 0 <= grid[i][j] <= 15
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/magic-squares-in-grid
 */
public class 矩阵中的幻方 {

    public static int numMagicSquaresInside(int[][] grid) {
        int nums = 0;
        if (grid.length < 2) return nums;
        int width = grid[0].length;
        // 矩阵大小为 i, 当 i = 3 时
        for (int i = 3;;){
            for (int j = 0 ; j <= grid.length-i; j++){
                for (int z = 0; z <= width-i; z++){
                    if (isMagix(j, j+i-1, z, z+i-1, grid)) nums++;
                }
            }
            break;
        }
        return nums;

    }

    /**
     * @param rstart 行起点
     * @param rend 行终点
     * @param lstart 列起点
     * @param lend 列终点
     * @return
     */
    private static boolean isMagix(int rstart, int rend, int lstart, int lend, int[][]grid){
        // 计算1-9
        if (!isNine(rstart, rend, lstart, lend, grid)) return false;
        // 计算行和
        int sum = rsum(lstart, lend, grid[rstart]);
        for (int i = rstart+1; i <= rend; i++){
            if (sum != rsum(lstart, lend, grid[i])) return false;
        }
        // 计算列
        for (int i = lstart; i <=lend; i++){
            if (sum != lsum(rstart, rend, i, grid)) return false;
        }
        // 计算对角线
        return isXSum(rstart, rend, lstart, lend, sum, grid);
    }

    private static boolean isXSum(int rstart, int rend, int lstart, int lend, int sum, int[][]a){
        int xsum = 0;
        for (int i = 0; i <= rend-rstart; i++){
            xsum += a[rstart+i][lstart+i];
        }
        if (xsum != sum) return false;
        xsum = 0;
        for (int i = 0; i <= rend-rstart; i++){
            xsum += a[rstart+i][lend-i];
        }
        return (xsum == sum);
    }

    private static int rsum(int start, int end, int[] a){
        int sum = 0;
        for (int i = start; i <=end; i++){
            sum += a[i];
        }
        return sum;
    }

    private static int lsum(int start, int end, int l, int[][] a){
        int sum = 0;
        for (int i = start; i <=end; i++){
            sum += a[i][l];
        }
        return sum;
    }

    private static boolean isNine(int rstart, int rend, int lstart, int lend, int[][]grid){
        boolean[] a = new boolean[10];
        for (int i = rstart; i <= rend; i ++){
            for (int j = lstart; j <= lend; j++){
                if (grid[i][j] <=9 && grid[i][j] >=1){
                    a[grid[i][j]] = true;
                }else {
                    return false;
                }

            }
        }
        for (int i = 1; i <=9; i ++){
            if (!a[i]) return false;
        }
        return true;
    }

    public static void main(String[] args){
        int[][] a = new int[][]{{4,3,8,4}, {9,5,1,9}, {2,7,6,2}};
        System.out.println(numMagicSquaresInside(a));
    }
}
